package version1;

/**
 * @author zhangjiayuan@qipeipu.com
 * @date 2019/1/14 8:32
 * @since 1.0.0
 */
public class Kmp3 {
    public static int[] Next(String p)
    {
        int[] next = new int[p.length()];
        next[0] = -1;
        int i = 0, j = -1;
        char[] pChar = p.toCharArray();
        while (i < p.length()-1)
        {
            if (j == -1 || pChar[i] == pChar[j])
            {
                i++;
                j++;
                next[i] = j;
            }
            else
                j = next[j];
        }
        return next;
    }

    public static void main(String[] args) {
        int[] next = Kmp3.Next("btbtbtru");
        for(int nextValue:next){
            System.out.println(nextValue);
        }
    }
}
